package org.example.SolutionNew007;

import java.util.*;

public class StackSolution001 {
    public static void main(String[] args) {
        StackSolution001 sol = new StackSolution001();
        String s="([])(";
        System.out.println(sol.isValid(s));
    }

    public boolean isValid(String s) {
        //用map来存储
        int n = s.length();
        if(n%2==1) return false;
        Deque<Character> stack = new LinkedList<>();

        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        for(int i=0; i<n; i++){
            char c=s.charAt(i);
            if(map.containsKey(c)){
                if(stack.isEmpty()||stack.peek()!=map.get(c)) return false;
                stack.pop();
            }else{
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
